//请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。 
//
// 
//
// 例如: 
//给定二叉树: [3,9,20,null,null,15,7], 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 
//
// 返回其层次遍历结果： 
//
// [
//  [3],
//  [20,9],
//  [15,7]
//]
// 
//
// 
//
// 提示： 
//
// 
// 节点总数 <= 1000 
// 
// Related Topics 树 广度优先搜索 二叉树 👍 173 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class CongShangDaoXiaDaYinErChaShuIiiLcof {
    public static void main(String[] args) {
        Solution solution = new CongShangDaoXiaDaYinErChaShuIiiLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 之字形打印二叉树，一行从右向左，零一行从左到右
     * 只使用queue时，可以在打印时进行反转
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode temp;
        int count;
        boolean flag = true;
        while (!queue.isEmpty()){
            count = queue.size();
            List<Integer> tempList = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                temp = queue.poll();
                tempList.add(temp.val);// 这里不会为空的
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
            if (!flag) Collections.reverse(tempList);//交替反转
            res.add(tempList);
            flag = !flag;
        }
        return res;
    }
    /**
     * 可以使用双端队列实现，或者只使用queue，然后打印的时候进行反转
     * 需要使用两个栈来实现，而且入栈方式有所不同
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> odd = new Stack<>();//奇数层节点
        Stack<TreeNode> even = new Stack<>();//偶数层节点
        TreeNode temp;
        boolean flag = true;
        odd.push(root);
        while (!odd.isEmpty() || !even.isEmpty()){
            List<Integer> list = new ArrayList<>();
            if (flag){//当前层为奇数层，下一层要逆序打印
                while (!odd.isEmpty()){
                    temp = odd.pop();
                    if (temp.left != null) even.push(temp.left);//左节点最后访问
                    if (temp.right != null) even.push(temp.right);
                    list.add(temp.val);
                }
            }else {//当前层为偶数层，下一层顺序打印
                while (!even.isEmpty()){
                    temp = even.pop();
                    if (temp.right != null) odd.push(temp.right);//右节点最后访问
                    if (temp.left != null) odd.push(temp.left);
                    list.add(temp.val);
                }
            }
            flag = !flag;
            res.add(list);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

}